#include <stdio.h>
#include <stdlib.h>

// 计数排序
// 仅整型适用
// 时间：O(N+Range)	当数据比较靠拢时使用最佳
// 例如[1000,999,1005,995,999]这样的 空间：O(Range)
void
CountSort(int* a, int n)
{
  // 找到数组a的最大和最小值
  int max = a[0], min = a[0];
  for (int i = 1; i < n; i++) {
    if (a[i] < min)
      min = a[i];
    if (a[i] > max)
      max = a[i];
  }

  // 开空间并在数的对应位置统计次数
  int range = max - min + 1;
  int* countArray = (int*)calloc(range, sizeof(int)); // 数组需初始化为全0
  if (countArray == NULL) {
    perror("calloc failed.\n");
    exit(-1);
  }
  for (int i = 0; i < n; i++) {
    countArray[a[i] - min]++; // 对应位置计数
  }

  // 遍历countArray，将索引拷贝回数组a
  int k = 0;
  for (int i = 0; i < range; ++i) {
    while (countArray[i]--) {
      a[k++] = i + min;
    }
  }

  free(countArray);
}

void
PrintArray(int* a, int n)
{
  for (int i = 0; i < n; ++i)
    printf("%d ", a[i]);
  printf("\n");
}

void
test_countSort()
{
  int arr[] = { -9, -4, 4, 1, 10, -8, -5, 4, 9, 6, 3, -3, -2 };
  int sz = sizeof(arr) / sizeof(int);
  PrintArray(arr, sz);
  CountSort(arr, sz);
  PrintArray(arr, sz);
}

int
main()
{
  test_countSort();
  return 0;
}